
// Definition for a Node.
class Node
{
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val)
    {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

// 法一 哈希 node : new_node 便利oldlist 处理random 和 next
#include <unordered_map>
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        std::unordered_map<Node *, Node *> u_map{{nullptr, nullptr}};
        for (Node *cur = head; cur; cur = cur->next)
            u_map[cur] = new Node(cur->val);
        for (Node *cur = head; cur; cur = cur->next)
        {
            u_map[cur]->random = u_map[cur->random];
            u_map[cur]->next = u_map[cur->next];
        }
        return u_map[head];
    }
};
// 法二 链接处理random 再分离
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        if (head == nullptr)
            return head;
        Node *cur = head;
        while (cur)
        {
            Node *next = cur->next;
            Node *new_node = new Node(cur->val);
            cur->next = new_node;
            new_node->next = next;
            cur = next;
        }
        cur = head;
        while (cur)
        {
            if (cur->random)
                cur->next->random = cur->random->next;
            else
                cur->next->random = nullptr;
            cur = cur->next->next;
        }
        Node *new_head = head->next;
        Node *pev = head;
        Node *new_pev = head->next;
        cur = new_head->next;
        while (cur)
        {
            new_pev->next = cur->next;
            pev->next = cur;
            pev = pev->next;
            new_pev = new_pev->next;
            cur = cur->next->next;
        }
        new_pev->next = pev->next = nullptr;
        return new_head;
    }
};